118 Pascal Triangle

題意為給整數 numRows，回傳一個包含前 numRows 層的 Pascal Triangle 的 List。
每一層的數字是由上一層相鄰兩數相加而來。

• Thinking
  • 第一層固定是 [1]。
  • 從第二層開始，每層的開頭與結尾是 1。
  • 中間的值是由上一層的兩個數相加：prev[i - 1][j - 1] + prev[i - 1][j]

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()

        for (i in 0 until numRows) {
            var row = MutableList(i+1) {1}
            for (j in 1 until i) {
                row[j] = triangle[i-1][j-1]+triangle[i-1][j]
            }
            triangle.add(row)
        }

        return triangle
    }
}

• 延伸題
  • 119 Pascal Triangle II
    • 給個 rowIndex（從 0 開始），回傳 Pascal Triangle 中的第 rowIndex 層的內容。
    • sol 1, 如上解法但僅回傳第 rowIndex 層內容
    • sol 2

    class Solution {
        fun getRow(rowIndex: Int): List<Int> {
            val row = MutableList(rowIndex+1) {0}
            row[0] = 1
            for (i in 1..rowIndex) {
                for (j in i downTo 1) {
                    row[j] = row[j] + row[j-1]
                }
            }
            return row
        }
    }
    

    • 為避免覆蓋更新過的值，從後往前更新是關鍵
    • 這種做法只用了 O(rowIndex) 的空間，符合題目進階要求。

  // 120 triangle minimum path sum
  // 62 Unique Paths
  // 1641 Count Sorted Vowel Strings
  // 931 Minimum Falling Path Sum
  // 1269 Number of Ways  to  Stay in the Same Place After Some Steps
  // 3463 Check If Digits Are Equal in String After Operations II (hard)
  // 2221 Find Triangular Sum of an Array